Theorem The problem of optimal reduction of combinatorial filters is
NP-hard.
Corollary . . . even if the filter is a tree.
Corollary . . . even if approximation is enough.
Corollary . . . even if some mistakes are OK.
Corollary . . . even if parameters are fixed.